// @algorithm @lc id=139 lang=cpp 
// @title word-break


// @test("leetcode",["leet","code"])=true
// @test("applepenapple",["apple","pen"])=true
// @test("catsandog",["cats","dog","sand","and","cat"])=false
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        dict.insert("");
        size_t maxlen = 0; // 最大单词长度
        for(auto & word : wordDict){
            dict.insert(word);
            maxlen = max(maxlen, word.size());
        }
        list<int> dp; // 有效单词右界(end)
        dp.push_back(0); // 空串视为有效
        for(int i=0; i<=s.size(); i++){
            for(auto it=dp.rbegin(); it!=dp.rend(); it++){
                if(dict.count(s.substr(*it, i-*it))){
                    dp.push_back(i);
                    break;
                }
                if(i-*it>=maxlen) break;
            }
        }
        return dp.back() == s.size();
    }
};